package com.nanxhs.structure.tree;

import lombok.Data;

import java.util.Objects;

/**
 * @author 唐海斌
 * @version 1.0
 * @date 2021/5/25 10:31
 */
public abstract class Tree {

    protected TreeNode root;
    /**
     * 添加元素
     * @param element
     */
    abstract void add(int element);

    /**
     * 删除元素
     * @param element
     */
    abstract void remove(int element);

    /**
     * 获取前序遍历迭代器
     * @return
     */
    public FirstIterator firstIterator() {
        return new FirstIterator(root);
    }

    /**
     * 获取中序遍历迭代器
     * @return
     */
    public MiddleIterator middleIterator() {
        return new MiddleIterator(root);
    }

    /**
     * 获取后续遍历迭代器
     * @return
     */
    public LastIterator lastIterator() {
        return new LastIterator(root);
    }

    /**
     * 获取层级遍历迭代器
     * @return
     */
    public TopIterator topIterator() {
        return new TopIterator(root);
    }
    /**
     * 查找
     * @param element
     * @return
     */
    public boolean search(int element) {
        return search(element, root, 0);
    }

    private boolean search(int element, TreeNode currentNode, int loopCount) {
        if (currentNode == null) {
            return false;
        }
        ++loopCount;
        if (Objects.equals(element, currentNode.element)) {
            System.out.println("遍历:" + loopCount + "次, 查找到元素:" + element);
            return true;
        }
        if (element > currentNode.element) {
            return search(element, currentNode.childrenRight, loopCount);
        } else {
            return search(element, currentNode.childrenLeft, loopCount);
        }
    }

    @Data
    public static class TreeNode {
        /**
         * 父节点
         */
        private TreeNode parent;
        /**
         * 子左节点
         */
        private TreeNode childrenLeft;
        /**
         * 子右节点
         */
        private TreeNode childrenRight;
        /**
         * 元素
         */
        private Integer element;
        /**
         * 平衡因子
         */
        private int balanceFactor;

        @Override
        public String toString() {
            return "TreeNode{}";
        }
    }
}
